import { cbtPrint } from "hy-algokit";
import IHeap from "./IHeap";

/**
 * 堆结构
 * 公式
 * 父节点：parent(i) = Math.floor((i - 1) / 2)
 * 左子节点：leftChild(i) = 2 * i + 1
 * 右子节点：rightChild(i) = 2 * i + 2
 */

class Heap<T> implements IHeap<T> {
  private _data: T[] = [];
  private _size: number = 0;

  private swap(i: number, j: number): void {
    const temp = this._data[i];
    this._data[i] = this._data[j];
    this._data[j] = temp;
  }

  insert(value: T): void {
    this._data.push(value);
    this._size++;

    let index = this._size - 1;

    this.hearfy_up(index);
  }

  private hearfy_up(index: number = this._size - 1): void {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this._data[index] <= this._data[parentIndex]) {
        break;
      }
      if (this._data[index] > this._data[parentIndex]) {
        this.swap(index, parentIndex);
        index = parentIndex;
      }
    }
  }

  extract(): T | undefined {
    if (this._size === 0) {
      return undefined;
    }
    if (this._size === 1) {
      this._size--;
      return this._data.pop() as T;
    }

    const topValue = this._data[0];
    this._data[0] = this._data.pop() as T;
    this._size--;

    this.hearfy_down();

    return topValue;
  }

  private hearfy_down(index: number = 0): void {
    let start = index;
    while (2 * start + 1 < this._size) {
      const childIndexLeft = start * 2 + 1;
      const childIndexRight = childIndexLeft + 1;
      let largerIndex = childIndexLeft;
      if (
        childIndexLeft < this._size &&
        this._data[childIndexLeft] <= this._data[childIndexRight]
      ) {
        largerIndex = childIndexRight;
      }

      if (this._data[start] >= this._data[largerIndex]) {
        break;
      }

      this.swap(index, largerIndex);
      start = largerIndex;
    }
  }

  peek(): T | undefined {
    return this._data[0];
  }

  isEmpty(): boolean {
    return this._size === 0;
  }

  get length(): number {
    return this._size;
  }

  build_heap(array: T[]): void {}

  print(): void {
    // console.log(this._data);
    cbtPrint(this._data);
  }
}

const arr = [19, 100, 36, 17, 3, 25, 1, 2, 7];
const heap = new Heap<number>();

arr.forEach((item) => {
  heap.insert(item);
});

heap.print();

console.log(heap.extract());
console.log(heap.extract());
console.log(heap.extract());
console.log(heap.extract());

export {};
